20240608 3040 - Medium - Array

3040. Maximum Number of Operations With the Same Score II

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        @cache
        def backtrace(i, j, score):
            if i >= j:
                return 0
            if score == -1:
                return 1 + max(backtrace(i+2, j, nums[i]+nums[i+1]), backtrace(i+1, j-1, nums[i]+nums[j]), backtrace(i, j-2, nums[j]+nums[j-1]))
            ans = 0 
            if nums[i] + nums[i+1] == score:
                ans = max(ans, 1 + backtrace(i+2, j, score))
            if nums[i] + nums[j] == score:
                ans = max(ans, 1 + backtrace(i+1, j-1, score))
            if nums[j] + nums[j-1] == score:
                ans = max(ans, 1 + backtrace(i, j-2, score))
            return ans
        return backtrace(0, len(nums)-1, -1)